package practice_2025_8_27;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 使用队列来辅助进行层序遍历
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> list = new ArrayList<>();
            while(sz-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }

    // 递归进行翻转，先翻转后面的，再翻转当前的，再连接
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }
        // 找到后续要翻转的头节点
        ListNode nextHead = head;
        int count = 0;
        while(count++ < k && nextHead != null) {
            nextHead = nextHead.next;
        }
        // 无需翻转，直接返回
        if (count <= k) {
            return head;
        }
        ListNode last = reverseKGroup(nextHead, k);
        // 利用头插进行翻转
        ListNode newHead = new ListNode(0);
        ListNode cur = head;
        count = 0;
        while(count++ < k) {
            ListNode next = newHead.next;
            newHead.next = cur;
            cur = cur.next;
            newHead.next.next = next;
        }
        head.next = last;
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
 }